Міністерство освіти і науки України
Національний Університет «Львівська Політехніка»
Кафедра ЕОМ
Контрольно-розрахункова робота
з дисципліни « Прикладна теорія цифрових автоматів»
(частина 2, завдання 2)
2005
2.2 Мінімізувати за допомогою методу Квасна-Мак-Класкі-Петрика функцію 5-ти змінних. Побудувати таблицю, яка ілюструє процес знаходження простих імплікант, і таблицю покриття. За допомогою метода Петрика визначити всі мінімальні розв’язки
Виконання роботи
Побудова простих імплікант
F=0011 1000 0100 1000 0011 0101 0100 1000- функція, яку потрібно мінімізувати. Нехай вона задана в Таблиці 1
Таблиця 1
№
a b c d e
f
0
0 0 0 0 0
0
1
0 0 0 0 1
0
2
0 0 0 1 0
1 (x)
3
0 0 0 1 1
1
4
0 0 1 0 0
1
5
0 0 1 0 1
0 (x)
6
0 0 1 1 0
0
7
0 0 1 1 1
0
8
0 1 0 0 0
0 (х)
9
0 1 0 0 1
1
10
0 1 0 1 0
0
11
0 1 0 1 1
0 (х)
12
0 1 1 0 0
1
13
0 1 1 0 1
0
14
0 1 1 1 0
0 (х)
15
0 1 1 1 1
0
16
1 0 0 0 0
0
17
1 0 0 0 1
0(х)
18
1 0 0 1 0
1
19
1 0 0 1 1
1
20
1 0 1 0 0
0(х)
21
1 0 1 0 1
1
22
1 0 1 1 0
0
23
1 0 1 1 1
1(х)
24
1 1 0 0 0
0
25
1 1 0 0 1
1
26
1 1 0 1 0
0(х)
27
1 1 0 1 1
0
28
1 1 1 0 0
1
29
1 1 1 0 1
0(х)
30
1 1 1 1 0
0
31
1 1 1 1 1
0
У Таблиці 2 позначено графи :
A b c d e- код набору
С- склеюванням яких наборів цей код утворився;
П- умовне позначення набору;
У-позначка про участь набору у склеюванні
В отриманій таблиці знаходяться всі імпліканти функції, які мають вигляд кон’юнкцій. Простими лише будуть ті з них, котрі не мають позначки /.
Таблиця 2
a b c d e
У
С
П
a b c d e
У
С
П
a b c d e
a0
00010
\
a0b0
e0
0001-
/
e0h10
j0
-001-
a1
00100
\
a0b5
e1
-0010
/
e1h1
j1
-001-
a2
01000
\
a1b1
e2
0010-
/
e2h12
j2
-010-
b0
00011
\
a1b3
e3
0-100
/
e3h13
j3
--100
b1
00101
\
a1b6
e4
-0100
/
e4h2
j4
-010-
b2
01001
\
a2b2
e5
0100-
e4h6
j5
--100
b3
01100
\
a2b3
e6
01-00
h8k1
g0
1--01
b4
10001
\
b0c0
h0
0-011
b5
10010
\
b0c2
h1
-0011
/
b6
10100
\
b1c3
h2
-0101
/
c0
01011
\
b2c0
h3
010-1
c1
01110
\
b2c4
h4
-1001
c2
10011
\
b3c1
h5
011-0
c3
10101
\
b3c6
h6
-1100
/
c4
11001
\
b4c2
h7
100-1
c5
11010
\
b4c3
h8
10-01
/
c6
11100
\
b4c4
h9
1-001
d0
10111
\
b5c2
h10
1001-
/
d1
11101
\
b5c5
h11
1-010
b6c3
h12
1010-
/
b6c6
h13
1-100
/
c2d0
k0
10-11
c4d1
k1
11-01
/
c6d1
k2
1110-
Прості імпліканти:
/ab/c/d, /ab/d/, /a/cde, /ab/ce, b/c/de, /abc/e, a/b/ce, a/b/ce, a/cd/e, a/bde, abc/d, /b/cd, c/d/e, /bc/d, a/de
які відповідають наборам
0100-,01-00,0-011,010-1,-1001,011-0,100-1,1-001,1-010,10-11,1110-,-001-,--100,
-010-,1--01
Формування мінімальної ДНФ
Позначимо через І1,І2,...І15 всі прості імпліканти функції f. Побудуємо таблицю покриття по функції f.( Таблиця 3) Її рядки відповідають одиничним наборам функції, а графи простим імплікантам. На схрещенні рядка і графи проставимо +, якщо імпліканта покриває набір.
a b c d e
I 1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
I12
I13
I14
I15
Одиничний розряд
/ab/c/d
/ab/d/e
/a/cde
/ab/ce
b/c/de
/abc/e
a/b/ce
a/b/ce
a/cd/e
a/bde
abc/d
/b/cd
c/d/e
/bc/d
a/de
0100-
01-00
0-011
010-1
-1001
011-0
100-1
1-001
1-010
10-11
1110-
-001-
--100
-010-
1--01
00011
+
+
00100
+
+
01001
+
+
+
01100
+
+
+
10010
+
+
10011
+
+
+
10101
+
+
11001
+
+
+
11100
+
Літер в імплікації
4
4
4
4
4
4
4
4
4
4
4
3
3
3
3
F=(i3&i12)(i13&i14)(i1&i4&i5)(i2&i6&i13)(i9&i12)(i7&i10&i12)(i14&i15)(i5&i8...
